package org.lql.algo.codecrush.hot100.graphTheory;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: liangqinglong
 * @date: 2025-09-16 00:35
 * @description: 994. 腐烂的橘子 <a href="https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class OrangesRotting {

	private final int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	private int[][] grid;
	private int row;
	private int col;
	private int freshCount;

	public int orangesRotting(int[][] grid) {
		if (grid == null || grid.length == 0) {
			return -1;
		}
		this.grid = grid;
		this.row = grid.length;
		this.col = grid[0].length;
		Queue<int[]> queue = new LinkedList<>();
		freshCount = 0;
		// 初始化队列和新鲜橘子的数量
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (grid[i][j] == 2) {
					queue.offer(new int[]{i, j});
				} else if (grid[i][j] == 1) {
					freshCount++;
				}
			}
		}
		// 分钟数
		int minutes = 0;
		while (!queue.isEmpty() && freshCount > 0) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				int[] point = queue.poll();
				int x = point[0];
				int y = point[1];
				spreadRottingOranges(queue, x, y);
			}
			minutes++;
		}
		return freshCount == 0 ? minutes : -1;
	}

	private void spreadRottingOranges(Queue<int[]> queue, int sx, int sy) {
		for (int[] direction : directions) {
			int nx = sx + direction[0];
			int ny = sy + direction[1];
			// 检查相邻橘子是否在范围内且为新鲜橘子，如果是则将其腐烂并加入队列
			if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 1) {
				// 标记为腐烂
				grid[nx][ny] = 2;
				// 加入队列以继续腐烂
				queue.offer(new int[]{nx, ny});
				// 更新新鲜橘子数量
				freshCount--;
			}
		}
	}

	public static void main(String[] args) {
		int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
		OrangesRotting orangesRotting = new OrangesRotting();
		int result = orangesRotting.orangesRotting(grid);
		System.out.println(result);
	}
}
